#include <bits/stdc++.h>
using namespace std;

/*
3397. 执行操作后不同元素的最大数量
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums 和一个整数 k。

你可以对数组中的每个元素 最多 执行 一次 以下操作：

将一个在范围 [-k, k] 内的整数加到该元素上。
返回执行这些操作后，nums 中可能拥有的不同元素的 最大 数量。

 

示例 1：

输入： nums = [1,2,2,3,3,4], k = 2

输出： 6

解释：

对前四个元素执行操作，nums 变为 [-1, 0, 1, 2, 3, 4]，可以获得 6 个不同的元素。

示例 2：

输入： nums = [4,4,4,4], k = 1

输出： 3

解释：

对 nums[0] 加 -1，以及对 nums[1] 加 1，nums 变为 [3, 5, 4, 4]，可以获得 3 个不同的元素。

 

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109
0 <= k <= 109
*/

// 法一
class Solution {
public:
    using ll = long long;
    int maxDistinctElements(vector<int>& nums, int k) {
        // sort + 贪心
        // 方便依次确定不重叠的目标值
        sort(nums.begin(), nums.end());
        ll prev_target = -1e18;         // 前一个元素的目标值
        int max_count = 0;              // 不同元素的最大数量

        for (int num : nums) {
            // 当前元素能到达的最小目标值
            ll min_possible = num - k;
            ll desired_target = max(min_possible, prev_target + 1);

            // 期望目标在当前元素limit  右边界为num + k
            if (desired_target <= num + k) {
                max_count++;
                prev_target = desired_target;   // 更新前一个目标值，为下一个元素做准备
            }
            // 当前元素无论怎么操作都会与前一个目标值重叠，跳过
        }
        return max_count;
    }
};

// 法二
// 输入输出加速优化：关闭同步流，取消cin与cout的绑定，提升输入输出效率
static const auto io_speed_up = []() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

class Solution {
public:
    int maxDistinctElements(vector<int>& nums, int k) {
        // 排序：让元素按从小到大有序，为后续贪心选择不重叠的目标值打基础
        sort(nums.begin(), nums.end());
        int count = 0; // 统计最终不同元素的数量
        // 初始目标值：设为第一个元素操作范围（[nums[0]-k, nums[0]+k]）的左侧外，确保第一个元素能被选中
        int target = nums[0] - k - 1;
        
        for (auto& n : nums) {
            int minNum = n - k; // 当前元素通过操作能达到的最小可能值（操作范围左边界）
            // 情况1：当前元素的最小可能值 > 前一个目标值，无重叠，直接选最小可能值为新目标
            if (minNum > target) {
                target = minNum; // 更新目标值为当前元素的最小可能值
                count++; // 新增一个不同元素
            } 
            // 情况2：最小可能值与前目标重叠，尝试选「前目标+1」（确保不重复）
            else {
                int t = target + 1; // 期望的新目标值（比前一个大1，避免重叠）
                int maxNum = n + k; // 当前元素操作范围的右边界
                // 若期望目标值在当前元素的操作范围内，则选中
                if (t <= maxNum) {
                    target = t; // 更新目标值
                    count++; // 新增一个不同元素
                }
                // 否则：当前元素无法找到不重叠的目标值，跳过
            }
        }
        return count; // 返回最大不同元素数量
    }
};